/*
 * @lc app=leetcode.cn id=61 lang=typescript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

//  思路：快慢指针
//  第一次遍历计算出链表长度，对k进行处理
//  通过快慢指针计算出断开点，并对最后一个的next为空

//  复杂度：O(n) O(1)
function rotateRight(head: ListNode | null, k: number): ListNode | null {
    let fast = head, slow = head, len = 0

    if (!head || !k) return head

    // 计算长度
    while (fast) {
        fast = fast.next
        len++
    }
    fast = head
    k %= len

    // 快指针先走k步
    while (k-- && fast.next) fast = fast.next
    while (fast && fast.next) {
        fast = fast.next
        slow = slow!.next
    }
    fast.next = head
    const newHead: ListNode | null = slow!.next
    slow!.next = null
    return newHead
};
// @lc code=end

import { ListNode } from './type'
let l1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))))
let l2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))))
console.log(ListNode.printList(rotateRight(l1, 2)))
console.log(ListNode.printList(rotateRight(l2, 1)))